#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;

//买卖股票的最佳时机含手续费
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
// class Solution {
// public:
//     int maxProfit(vector<int>& prices, int fee) {
//         int n = prices.size();
//         if (n < 2) return 0;

//         vector<int> f(n), g(n); //f表示在第i天购入股票，g表示在第i天售出股票
//         f[0] = -prices[0];
//         for (int i = 1; i < n; ++i)
//         {
//             f[i] = max(f[i - 1], g[i - 1] - prices[i]); //要么卖出股票，要么买入后什么也不做
//             g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee); //要么买入股票，要么卖出后什么也不做
//         }
//         return max(f[n - 1], g[n - 1]);
//     }
// };


//买卖股票的最佳时机III
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         int n = prices.size();
//         if(n<2) return 0;

//         vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f3f)),g(n,vector<int>(3,-0x3f3f3f3f));
//         f[0][0] = -prices[0];
//         g[0][0] = 0;
//         for(int i = 1;i<n;++i)
//             for(int k=0;k<3;++k)
//             {
//                 f[i][k] = max(f[i-1][k],g[i-1][k]-prices[i]); //买入股票和什么股票都没有
//                 g[i][k] = g[i-1][k]; //可交易先于昨天的状态相等
//                 if(k-1>=0) g[i][k] = max(g[i-1][k],f[i-1][k-1]+prices[i]); //要么今天不卖股票，要么卖出
//             }

//         return max(max(g[n-1][0],g[n-1][1]),g[n-1][2]);
//     }
// };
//优化
// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         int m = prices.size();
//         if(m < 2) return 0; //低于2个股票收益为0 

//         int n = 3; //限定只能交易2次(开区间)

//         //f为买入股票 g为售出股票(售出一次算交易一次)
//         //初始化为最小值 放置第一次购买股票时f初始化为负数 后面的结果全部都为0
//         vector<vector<int>> f(m,vector<int>(n,-0x3f3f3f3f)),g(m,vector<int>(n,-0x3f3f3f3f));
//         f[0][0] = -prices[0];
//         g[0][0] = 0;
//         int maxnum = 0;
//         for(int i = 1;i<m;++i)
//             for(int k = 0;k<n;++k)
//             {
//                 //买入阶段-要么不买(继承昨天的对应次数相同状态)，要么买入
//                 f[i][k] = max(f[i-1][k],g[i-1][k]-prices[i]);
//                 g[i][k] = g[i-1][k]; //可交易阶段先继承状态对应次数状态(在可交易下什么都不做)
//                 //选择是否进行交易 交易需要昨天的第k-1次交易
//                 if(k-1>=0) g[i][k] = max(g[i-1][k],f[i-1][k-1]+prices[i]); //如果不是第0次可交易则求保持和交易哪个收益最大
//                 if(g[i][k] > maxnum) maxnum = g[i][k];
//             }

//         return maxnum;
//     }
// };


//买卖股票的最佳时机IV
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/submissions/
//class Solution {
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        int m = prices.size();
//        if (m < 2) return 0; //低于2个股票收益为0 
//
//        //因为一次买入和卖出才算一次交易，当只有20天让我们交易30次是不可能的，只有20天只能交易10次(10/2)
//        int n = min(k, m / 2); //优化次数
//
//        //f为买入股票 g为售出股票(售出一次算交易一次)
//        //初始化为最小值 放置第一次购买股票时f初始化为负数 后面的结果全部都为0
//        vector<vector<int>> f(m, vector<int>(n + 1, -0x3f3f3f3f)), g(m, vector<int>(n + 1, -0x3f3f3f3f)); //由于存在奇数问题，这里n+1
//        f[0][0] = -prices[0];
//        g[0][0] = 0;
//        int maxnum = 0;
//        for (int i = 1; i < m; ++i)
//            for (int j = 0; j <= n; ++j)
//            {
//                //买入阶段-要么不买(继承昨天的对应次数相同状态)，要么买入
//                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
//                g[i][j] = g[i - 1][j]; //可交易阶段先继承状态对应次数状态(在可交易下什么都不做)
//                //选择是否进行交易 交易需要昨天的第k-1次交易
//                if (j - 1 >= 0) g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]); //如果不是第0次可交易则求保持和交易哪个收益最大
//                if (g[i][j] > maxnum) maxnum = g[i][j]; //因为f是持有股票，持有股票不可能是最大的，g中卖出一定是最大的
//            }
//
//        return maxnum;
//    }
//};